package com.aug_leo.datastructure.priorityqueue;

import com.aug_leo.datastructure.queue.Queue;

import java.util.Arrays;

/**
 * 基于<b>大顶堆</b>实现
 *
 * @param <E> 队列中元素类型, 必须实现 Priority 接口
 */
@SuppressWarnings("all")
public class PriorityQueue3<E extends Priority> implements Queue<E> {

    /**
     * 存储队列元素的数组
     */
    Priority[] array;

    /**
     * 队列中元素的数量
     */
    int size;

    public PriorityQueue3(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public String toString() {
        return Arrays.toString(array);
    }

    /**
     * 向队列尾插入值. 有的习惯命名为 enqueue
     *
     * @param offered 待插入值
     * @return 插入成功返回 true, 插入失败返回 false
     */
    @Override
    public boolean offer(E offered) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int paraent = (child - 1) / 2;
        while (child > 0 && offered.priority() > array[paraent].priority()) {
            array[child] = array[paraent];
            child = paraent;
            paraent = (child - 1) / 2;
        }

        array[child] = offered;
        return true;
    }

    /**
     * 从对列头获取值, 并移除. 有的习惯命名为 dequeue
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, --size);
        E e = (E) array[size];
        array[size] = null; // help GC

        // 下潜
        down(0, array[0]);

        return e;
    }


    /**
     * 下潜操作，用于维持优先队列的性质
     * 比较父节点与其子节点的优先级，如果子节点的优先级大于父节点，则进行交换
     *
     * @param paraent 当前调整的父节点的索引
     * @param top     最终要放置在父节点位置的对象，可能是原父节点或子节点
     */
    private void down(int paraent, Priority top) {
        // 计算父节点的左子节点索引
        int left = 2 * paraent + 1;
        // 计算父节点的右子节点索引
        int right = left + 1;
        // 假设父节点拥有最大优先
        int max = paraent;

        // 两个孩子里找个大的
        // 如果左子节点存在，并且优先级大于父节点，则认为左子节点较大
        if (left < size) {
            max = left;
            // 如果右子节点存在，并且优先级大于左子节点，则认为右子节点最大
            if (right < size && array[right].priority() > array[left].priority()) {
                max = right;
            }
        }
        // 如果最大值不是父节点，并且最大值的优先级大于top的优先级，则进行向下调整
        if (max != paraent && array[max].priority() > top.priority()) {
            // 将最大值的孩子上移至父节点位置
            array[paraent] = array[max];
            // 继续向下调整新的父节点
            down(max, top);
        } else {
            // 如果没有孩子，或者孩子没有top大，则将top放置在父节点位置
            array[paraent] = top;
        }
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 从对列头获取值, 不移除
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    /**
     * 检查队列是否为空
     *
     * @return 空返回 true, 否则返回 false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return 满返回 true, 否则返回 false
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
